package com.sheng.leetcode.year2022.month09.day13;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/09/13
 *<p>
 * 670. 最大交换<p>
 *<p>
 * 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。<p>
 *<p>
 * 示例 1 :<p>
 * 输入: 2736<p>
 * 输出: 7236<p>
 * 解释: 交换数字2和数字7。<p>
 * <p>
 * 示例 2 :<p>
 * 输入: 9973<p>
 * 输出: 9973<p>
 * 解释: 不需要交换。<p>
 * 注意:<p>
 *<p>
 * 给定数字的范围是[0, 108]<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximum-swap">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0670 {

    @Test
    public void test01() {
//        int num = 2736;
//        int num = 9973;
//        int num = 98368;
        int num = 1993;
        System.out.println(new Solution().maximumSwap(num));
    }
}
class Solution {
    public int maximumSwap(int num) {
        // 将num转化为字符串
        String str = String.valueOf(num);
        // 将字符串转换为char数组
        char[] chars = str.toCharArray();
        // 字符串长度
        int length = str.length();
        // 对char数组进行排序
        Arrays.sort(chars);
        // 不符合的索引
        int index = -1;
        for (int i = 0; i < length; i++) {
            // 找到与字符从大到小顺序不一样的第一个位置，并用index记录，然后跳出循环
            if (chars[length - 1 - i] != str.charAt(i)) {
                index = i;
                break;
            }
        }
        // 等于-1说明num就是最大的，直接返回
        if (index != -1) {
            // c代表不符合的字符
            char c = str.charAt(index);
            // max代表c之后的字符中最大的最靠后的字符
            char max = str.charAt(index);
            // x为max的索引
            int x = -1;
            // 找到所需字符
            for (int i = index + 1; i < length; i++) {
                if (str.charAt(i) >= max) {
                    max = str.charAt(i);
                    x = i;
                }
            }
            // 找到，则进行排序
            if (x != -1) {
                // 将index和x位置的字符交换顺序
                char[] chars1 = str.toCharArray();
                chars1[index] = max;
                chars1[x] = c;
                String s = String.copyValueOf(chars1);
                return Integer.parseInt(s);
            }
        }
        return num;
    }
}
